import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    /**
     * 矩阵区域和 给定一个k来计算往外k圈的总和
     * 采用了 二维前缀和的方法
     * 先用一个二维数组计算好所有位置的前缀和dp数组，切记这个dp数组是从[1,1]下标开始的，所以在计算answer数组的时候 注意下标别错了
     * @param mat
     * @param k
     * @return
     */
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length,n = mat[0].length;
        int[][] answer = new int[m][n];

        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] -
                        dp[i-1][j-1] + mat[i-1][j-1];
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 因为这个dp数组是从[0，0]开始的，所以说可以把x1,x2,y1,y2加一。
                int x1 = Math.max(0,i - k) + 1;
                int y1 = Math.max(0,j-k) + 1;
                int x2 = Math.min(m-1,i+k) + 1;
                int y2 = Math.min(n-1,j+k) + 1;
                answer[i][j] = dp[x2][y2] -
                        dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }
        return answer;
    }


    /**
     * 连续数组 525题
     * 采用了 前缀和+哈希表的方法
     * 最优先可以将数组中的0当做成-1，这样的话可以计算和为0的最长子数组即可
     * 随后算好到i这个位置的sum所有值，然后在哈希表中找到之前的和为sum的值即可，与计数变量count进行比较 取最大值.
     * @param nums
     * @return
     */
    public int findMaxLength(int[] nums) {
        int sum = 0;
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        for (int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 0 ? -1 : 1);
            if(map.containsKey(sum))
                count = Math.max(count,i - map.get(sum));
            else map.put(sum,i);
        }

        return count;
    }
}